In recent years, investigation of a MIMO (Multiple Input Multiple Output) technique has been and is being carried out energetically as a next generation communication technique.
In the MIMO system, a plurality of data streams are transmitted from a transmitter including a plurality of transmission antennas and are separated and received by a receiver including a plurality of reception antennas.
An example of a configuration of the MIMO system is illustrated in FIG. 1.
The MIMO system 10 illustrated in FIG. 1 illustratively includes a transmitter 20 having a plurality of transmission antennas 21-1, 21-2, . . . , and 21-M (M is an integer equal to or higher than two) and a receiver 30 having a plurality of reception antennas 31-1, 31-2, . . . , and 31-N (N is an integer equal to or higher than two). It is to be noted that, in the following description, where the transmission antennas 21-1, 21-2, . . . and 21-M are not distinguished from each other, they are described simply as transmission antennas 21, and, where the reception antennas 31-1, 31-2, . . . and 31-M are not distinguished from each other, the reception antennas are described simply as reception antennas 31.
Further, in order to simplify the description, it is assumed as an example that the transmitter 20 transmits M data streams equal to the number of the transmission antenna 21 while the receiver 30 receives N reception signals equal to the number of the reception antenna 31. However, it is assumed that the following expression is satisfied:M≦N 
Here, if a vector x of M rows and one column including M data streams x1 to xM as component elements, a channel matrix H of N rows and M columns including propagation path gains hζξ between the ξth (1≦ξ≦M) transmission antennas and the ξth (1≦ζ≦N) reception antennas as component elements, a vector y of N rows and one column including reception signals y1 to yN as component elements and a vector n of N rows and one column including noise n1 to nN as component elements are defined, then the following expressions (1) and (2) are obtained:
                    y        =                  Hx          +          n                                    (        1        )                                          (                                                                      y                  1                                                                                                      y                  2                                                                                    ⋮                                                                                      y                  N                                                              )                =                                            (                                                                                          h                      11                                                                                                  h                      12                                                                            …                                                                              h                                              1                        ,                        M                                                                                                                                                        h                      21                                                                                                  h                      22                                                                            …                                                                              h                                              2                        ,                        M                                                                                                                                  ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                                              h                                              N                        ,                        1                                                                                                                        h                                              N                        ,                        2                                                                                                  …                                                                              h                                              N                        ,                        M                                                                                                        )                        ⁢                          (                                                                                          x                      1                                                                                                                                  x                      2                                                                                                            ⋮                                                                                                              x                      M                                                                                  )                                +                      (                                                                                n                    1                                                                                                                    n                    2                                                                                                ⋮                                                                                                  n                    N                                                                        )                                              (        2        )            
Meanwhile, as a method for separating a data stream on the receiver 30 side, for example, an MMSE (Minimum Mean Square Error) method or an MLD (Maximum Likelihood Detection) method is available.
In the MMSE method, a data stream is separated by multiplying a received signal by a predetermined coefficient based on mean square error criteria.
In the MLD method, a metric such as a square Euclidean distance is calculated for combinations of all symbol replica candidates of a plurality of data streams and a combination of those symbol replica candidates which minimizes the total of the metrics is determined as a signal after the data stream separation.
By the MLD method, an excellent reception performance can be obtained in comparison with a linear separation method such as the MMSE method and so forth. However, if a modulation multi-value number of the lth (1≦l≦M) transmission signal is represented by gl, then the number of combinations of the symbol replica candidates is calculated by
      ∏          l      =      1        M    ⁢          ⁢            g      l        .  
It is to be noted that, in the case of QPSK (Quadrature Phase Shift Keying), g1=4, in the case of 16QAM (16 Quadrature Amplitude Modulation), g1=16, and in the case of 64QAM, g1=64.
Therefore, there is a case that, as the modulation level and the transmission data stream number increase, the number of times of calculation of the metric increases exponentially and the processing amount becomes enormous.
Therefore, various types of MLD methods have been proposed to reduce mathematical operation amount.
For example, in Non-Patent Document 1 listed below, a QRM-MLD (complexity-reduced Maximum Likelihood Detection with QR decomposition and the M-algorithm) method which is a combination of QR decomposition and the M-algorithm has been proposed.
In the QRM-MLD method, a metric such as a square Euclidean distance of all of symbol replica candidates with regard to surviving symbol replica candidates in the preceding stage is calculated.
Where the number of surviving symbol replica candidates in the kth (k=1, 2, . . . , M) stage is represented by Sk, the number of times of calculation of the metric by the QRM-MLD method is calculated by the following expression:
      g    1    +            ∑              k        =        1                    M        -        1              ⁢                  ⁢                  g                  k          +          1                    ⁢              S        k            
Meanwhile, in Non-Patent Document 2 listed below, an ASESS (Adaptive SElection of Surviving Symbol replica candidates based on the maximum reliability) method in which a further reduction method of the number of times of calculation of a metric is applied to the QRM-MLD method is disclosed.
According to the ASESS method, symbol replica candidates in each stage are ranked by quadrant decision and calculation of a metric is carried out by the number of surviving symbol replica candidates in order beginning with a symbol replica candidate whose cumulative value (sum total) of the metric is low.
Accordingly, the number of times of calculation of the metric in the ASESS method is calculated by the following expression:
      ∑          k      =      1        M    ⁢          ⁢      S    k  
In this manner, in the ASESS method, the number of times of calculation of a metric increases linearly with respect to the number of transmission data streams.
Further, in Patent Document 1 listed below, a method is proposed in which a plurality of transmission signal candidates are narrowed down stepwise by a predetermined number based on a proximity signal point data table which stores a corresponding relationship between estimated transmission signals of individual transmission systems and signal points which exhibit a short inter-signal point distance on a transmission constellation.    [Patent Document 1] Japanese Patent Laid-Open No. 2006-222872    [Non-Patent Document 1] K. J. Kim and J. Yue, “Joint channel estimation and data detection algorithms for MIMO-OFDM systems,” in Proc. Thirty-Sixth Asilomar Conference on Signals, Systems and Computers, pp. 1857-1861, November 2002    [Non-Patent Document 2] K. Higuchi, H. Kawai, N. Maeda and M. Sawahashi, “Adaptive Selection of Surviving Symbol Replica Candidates Based on Maximum Reliability in QRM-MLD for OFCDM MIMO Multiplexing,” Proc. of IEEE Globecom 2004, pp. 2480-2486, November 2004